The present invention relates to computers and, more particularly, to computers that execute branch instructions. A major objective of the invention is to enhance performance by improving predictions required for speculative processing, e.g., as used for pre-fetching data and instructions. Related art is discussed below to help explain a problem addressed by the present invention. Related art labeled as “prior art” is admitted prior art; related art not labeled as “prior art” is not admitted prior art.
Much of modern progress is associated with the pervasiveness of computers that manipulate data in accordance with programs of instructions. Given a never-ending demand for increased speed, the computer industry has taken pains to minimize delays in processing. In some cases, operations can be performed out of program order so the results are available as soon as they are required. For example, certain instructions and data can be pre-fetched into a cache before their execution is required; when they are called for, they can be accessed quickly from a cache instead more slowly from main memory. Many operations are not fully specified or known until the results of logically preceding operations are known. For example, an address pre-fetch might require determination of the results of a conditional branch instruction that has not yet been executed. In such cases, some speculative pre-processing can be performed advantageously when the outcome of the prerequisite operations can be predicted with sufficient success.
In a software approach to prediction, a program can include prediction hints in the instructions themselves. Typically, a compiler program provides these either in response to a programmer's specifications or in accordance with the program's analysis of the program structure. For example, a branch instruction can include a field that denotes “this branch is usually (or, alternatively, rarely) taken”. In a hardware approach to prediction, processing results can be tracked and the resulting processing history can be used to predict future results. For example, if a branch instruction has resulted in repeated returns to the beginning of a loop, the processor can pre-fetch the beginning of the loop the next time the branch instruction is encountered.
The hardware approach has access to recent runtime data, which is not available at compilation time. On the other hand, the compiler has access to the program as a whole, while the hardware typically has access to only a small portion of a program at a time. In practice, a processor should be able to access prediction results within a processor cycle or two. However, the memory available to store such results within this time requirement is very limited. As programs have grown exponentially over time, the portion of a program that can be represented by stored prediction results is growing smaller.